/**
 * 二叉搜索树
 */
module.exports = class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  /**
   * 插入节点
   * @param {number} key 节点值
   */
  insert(key) {
    // 创建一个新的节点
    const createdNode = new Node(key);

    /**
     * 插入节点递归函数
     * @param {Node} parentNode 节点
     * @param {Node} newNode 待插入的新节点
     */
    const insertNode = (parentNode, newNode) => {
      // 如果新节点存储值比父节点存储值小
      if (newNode.key < parentNode.key) {
        // 如果父节点的左侧，有子节点，则继续递归插入
        if (parentNode.left) {
          insertNode(parentNode.left, newNode);
        } else {
          parentNode.left = newNode;
        }
      } else {
        // 如果新节点存储值比父节点存储值大
        // 如果父节点的右侧，有子节点，则继续递归插入
        if (parentNode.right) {
          insertNode(parentNode.right, newNode);
        } else {
          parentNode.right = newNode;
        }
      }
    };

    // 如果根节点不为空，则向下递归
    if (this.root) {
      insertNode(this.root, createdNode);
    } else {
      this.root = createdNode;
    }
  }

  /**
   * 中序遍历
   * @param {Function} callback
   */
  inOrderTraverse(callback) {
    /**
     * 按中顺序遍历节点
     * @param {Node} node 节点
     * @param {Function} callback 回调函数
     */
    const inOrderTraverseNode = (node, callback) => {
      if (node) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
      }
    };
    inOrderTraverseNode(this.root, callback);
  }

  /**
   * 先序遍历
   * @param {Function} callback
   */
  preOrderTraverse(callback) {
    /**
     * 按先顺序遍历节点
     * @param {Node} node 节点
     * @param {Function} callback 回调函数
     */
    const preOrderTraverseNode = (node, callback) => {
      if (node) {
        callback(node.key);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
      }
    };
    preOrderTraverseNode(this.root, callback);
  }

  /**
   * 后序遍历
   * @param {Function} callback
   */
  postOrderTraverse(callback) {
    /**
     * 按后顺序遍历节点
     * @param {Node} node 节点
     * @param {Function} callback 回调函数
     */
    const postOrderTraverseNode = (node, callback) => {
      if (node) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback);
        callback(node.key);
      }
    };
    postOrderTraverseNode(this.root, callback);
  }

  /**
   * 搜索二叉树最小值
   * @param {Node} node 节点
   */
  min(node) {
    /**
     * 搜索二叉树拥有最小值的节点
     * @param {Node} node 节点
     */
    const minNode = node => {
      return node ? (node.left ? minNode(node.left) : node) : null;
    };
    return minNode(node || this.root);
  }

  /**
   * 搜索二叉树最大值
   * @param {Node} node 节点
   */
  max(node) {
    /**
     * 搜索二叉树拥有最大值的节点
     * @param {Node} node 节点
     */
    const maxNode = node => {
      return node ? (node.right ? maxNode(node.right) : node) : null;
    };
    return maxNode(node || this.root);
  }
};

class Node {
  /**
   * 节点构造函数
   * @param {number} key 节点值
   */
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
